import java.util.Scanner;

class ListNode {
    int data;
    ListNode next;

    public ListNode(int data) {
        this.data = data;
        this.next = null;
    }
}

public class LinkedListSequence {
    private ListNode head;
    private int size;
    private Scanner scanner;

    public LinkedListSequence() {
        head = null;
        size = 0;
        scanner = new Scanner(System.in);
    }

    // 1. 创建顺序表
    public void create() {
        System.out.print("请输入要创建的顺序表长度(>1): ");
        int length = scanner.nextInt();
        if (length <= 1) {
            System.out.println("长度必须大于1！");
            return;
        }

        System.out.print("请输入" + length + "个数（空格隔开,可无序输入）: ");
        for (int i = 0; i < length; i++) {
            int num = scanner.nextInt();
            append(num);
        }

        sort(); // 创建后自动排序
        System.out.println("创建成功！");
        print();
    }

    // 2. 插入元素
    public void insert() {
        System.out.print("请输入要插入的位置(从1开始)及元素: ");
        int position = scanner.nextInt();
        int element = scanner.nextInt();

        if (position < 1 || position > size + 1) {
            System.out.println("插入位置不合法！");
            return;
        }

        ListNode newNode = new ListNode(element);
        if (position == 1) {
            newNode.next = head;
            head = newNode;
        } else {
            ListNode current = head;
            for (int i = 1; i < position - 1; i++) {
                current = current.next;
            }
            newNode.next = current.next;
            current.next = newNode;
        }
        size++;
        System.out.println("插入成功！！！");
        print();
    }

    // 3. 删除元素
    public void delete() {
        System.out.print("请输入要删除的位置(从1开始): ");
        int position = scanner.nextInt();

        if (position < 1 || position > size) {
            System.out.println("删除位置不合法！");
            return;
        }

        if (position == 1) {
            head = head.next;
        } else {
            ListNode current = head;
            for (int i = 1; i < position - 1; i++) {
                current = current.next;
            }
            current.next = current.next.next;
        }
        size--;
        System.out.println("删除成功！！！");
        print();
    }

    // 4. 顺序查找
    public void sequentialSearch() {
        System.out.print("请输入要查找的值: ");
        int value = scanner.nextInt();

        ListNode current = head;
        int position = 1;
        while (current != null) {
            if (current.data == value) {
                System.out.println("该元素位置为: " + position);
                return;
            }
            current = current.next;
            position++;
        }
        System.out.println("未找到该元素！");
    }

    // 5. 折半查找（链表实现需要特殊处理）
    public void binarySearch() {
        System.out.print("请输入要查找的值: ");
        int value = scanner.nextInt();

        int left = 1;
        int right = size;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midValue = get(mid);
            if (midValue == value) {
                System.out.println("该元素位置为: " + mid);
                return;
            } else if (midValue < value) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        System.out.println("未找到该元素！");
    }

    // 获取指定位置的元素值
    private int get(int position) {
        ListNode current = head;
        for (int i = 1; i < position; i++) {
            current = current.next;
        }
        return current.data;
    }

    // 6. 倒置链表
    public void reverse() {
        ListNode prev = null;
        ListNode current = head;
        ListNode next = null;

        while (current != null) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        head = prev;
        System.out.println("倒置成功！");
        print();
    }

    // 7. 输出链表
    public void print() {
        System.out.print("当前顺序表所有元素: ");
        ListNode current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    // 8. 清空链表
    public void clear() {
        head = null;
        size = 0;
        System.out.println("链表已清空！");
    }

    // 9. 排序链表（使用插入排序）
    public void sort() {
        if (head == null || head.next == null) {
            return;
        }

        ListNode sorted = null;
        ListNode current = head;

        while (current != null) {
            ListNode next = current.next;
            if (sorted == null || sorted.data >= current.data) {
                current.next = sorted;
                sorted = current;
            } else {
                ListNode temp = sorted;
                while (temp.next != null && temp.next.data < current.data) {
                    temp = temp.next;
                }
                current.next = temp.next;
                temp.next = current;
            }
            current = next;
        }
        head = sorted;
        System.out.println("排序成功！！！");
    }

    // 添加元素到链表末尾
    private void append(int data) {
        ListNode newNode = new ListNode(data);
        if (head == null) {
            head = newNode;
        } else {
            ListNode current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
        size++;
    }

    // 显示菜单
    public void showMenu() {
        System.out.println("\n请选择你要的操作:");
        System.out.println("1. 创建");
        System.out.println("2. 插入");
        System.out.println("3. 删除");
        System.out.println("4. 顺序查找");
        System.out.println("5. 折半查找");
        System.out.println("6. 倒置");
        System.out.println("7. 输出");
        System.out.println("8. 清空");
        System.out.println("9. 排序");
        System.out.println("0. 退出");
        System.out.print(">>>请选择你的操作：");
    }

    public static void main(String[] args) {
        LinkedListSequence list = new LinkedListSequence();
        Scanner scanner = new Scanner(System.in);
        int choice;

        do {
            list.showMenu();
            choice = scanner.nextInt();

            switch (choice) {
                case 1:
                    list.create();
                    break;
                case 2:
                    list.insert();
                    break;
                case 3:
                    list.delete();
                    break;
                case 4:
                    list.sequentialSearch();
                    break;
                case 5:
                    list.binarySearch();
                    break;
                case 6:
                    list.reverse();
                    break;
                case 7:
                    list.print();
                    break;
                case 8:
                    list.clear();
                    break;
                case 9:
                    list.sort();
                    list.print();
                    break;
                case 0:
                    System.out.println("退出系统！");
                    break;
                default:
                    System.out.println("输入错误！");
            }
        } while (choice != 0);
    }
}